﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Sol112
{


    int sum = 0;
    public bool HasPathSum2(TreeNode root, int targetSum)
    {

        if (root == null)//说明到了叶子节点
        {
            if(sum==targetSum)
            {
                return true;
            }else { return false; }
        }

        sum = sum + root.val;//这样累加的方法，每次退栈的时候都要重新减去这次加上的val，并且targetSum永远不变，没有得到利用
        Console.WriteLine(sum);
        HasPathSum(root.left, targetSum);
        sum = sum - root.left.val;
        HasPathSum(root.right, targetSum);
        sum = sum - root.right.val;




        return false;

    }
    public bool HasPathSum3(TreeNode root, int targetSum)//DFS的递归法
    { 
    if(root == null)
        {
            return false;
        }
        if (root.left == null && root.right == null) { //叶子节点，判断一下
        

            return targetSum==root.val;

        }

     bool leftHasPathSum =   HasPathSum( root.left, targetSum-root.val );
        bool rightHasPathSum = HasPathSum( root.right, targetSum-root.val );


        return leftHasPathSum ||rightHasPathSum;//左右孩子有一个满足就行


    }
    public bool HasPathSum(TreeNode root, int targetSum)//BFS
    { 
    
        IList<TreeNode> queueNode = new List<TreeNode>();
        IList<int> queueSum = new List<int>();//记录各个叶子节点的sum

        if(root== null)
        {
            return false;
        }

        
        queueNode.Add(root);
        queueSum.Add(root.val);
        while (queueNode.Count > 0)
        {
            //出队
            root = queueNode[0];
           int curSum = queueSum[0];
            if (curSum == targetSum)
            {
                if (root.left == null && root.right == null)
                { //叶子节点，判断一下


                    return true;

                }
            }
            //sum=sum + root.val;//不可以加入到一个总共里面，只能加入对应路径的
            //Console.WriteLine("val:   " + root.val + "    sum: " + curSum);
            queueNode.RemoveAt(0);
            queueSum.RemoveAt(0);
            if(root.left != null)
            {
                queueNode.Add(root.left);//叶子节点入队的同时 ，对应的sum也入队
                queueSum.Add(root.left.val+curSum);
            }
          if(root.right != null)
            {
                queueNode.Add(root.right);
                queueSum.Add(root.right.val + curSum);
            }
            


        }


        return false;
    
    }

    }

class Program112
{

    static void Main112(string[] args)
    {
        string preOrder = "5 4 11 7 2 8 13 4 1";
        string[] chars = preOrder.Split(" ");
        int[] nums = new int[chars.Length];
        for (int i = 0; i < chars.Length; i++)
        {
            nums[i] = int.Parse(chars[i]);
        }

        int[] inOrder = { 7,11,2,4,5,13,8,4,1 };

        Solution105 solution105 = new Solution105();



        TreeNode root = solution105.BuildTree(nums, inOrder);

        //solution105.levelOrder(root);
        Sol112 solution = new Sol112();
        bool res= solution.HasPathSum(root, 22);
        Console.WriteLine(res);
    }
}